package Testdemo3.Test1;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:周次煜
 * Date: 2024-05-16
 * Time：23:17
 */
public class Test3 {
    public static void main(String[] args) {

    }


    /**
     * 求 泰波那锲数
     *
     * 方法一:
     * 挪变量法
     * 讲新的结果重新赋值
     * n0 取代 n1
     * n1 取代 n2
     * n2 取代 新更新出来的结果
     *
     *
     * @param n 求第几位
     * @return 返回 该位置的值
     *
     *
     */
    public int tribonacci(int n) {

        // 挪变量法
        int T0=0,T1=1,T2=1;
        int Tn=0;

        if(n==0) return 0;
        if(n==1 || n==2) return 1;

        // 循环累加
        while(n - 2 >= 1) {
            Tn= T1 + T2 + T0;
            T0 = T1;
            T1 = T2;
            T2 = Tn;
            // 进行挪动数据
            n--;
        }


        return Tn;

    }


    /**
     *
     * 泰波那契数
     *
     *
     * 方法二：
     * 利用前缀和的思想
     *
     * 把前几个值前缀和的数值进行累加即可
     *
     * @param n 需要求的下标位置
     * @return 返回该下标的前缀和
     *
     */

    public int tribonacci2(int n) {
        if(n==0) return 0;
        if(n==1 || n==2) return 1;


        // 前缀和
        int []dp = new int[n+1];
        dp[0]=0;
        dp[1]=1;
        dp[2]=1;


        // 循环累加
        for(int i = 3; i < n + 1 ; i++) {
            dp[i] = dp[i-1] + dp[i-2]+ dp[i-3];
        }


        return dp[n];

    }



}
